package map_set.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 复制带随机指针的链表
 * @author yuisama
 * @date 2022/03/11 19:45
 **/
public class Num138 {
    private class Node {
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        // 边界
        if (head == null) {
            return null;
        }
        // 遍历原链表，构造新链表的节点，存储在Map中
        // Map<原链表结点，新链表结点>
        // 原1 => 新1
        Map<Node,Node> nodeMap = new HashMap<>();
        for (Node x = head;x != null;x = x.next) {
            // 构造新链表的节点
            Node node = new Node(x.val);
            nodeMap.put(x,node);
        }
        // 对新链表进行连接操作
        // 原1.next 和新1.next一一对应
        // 原1.random 和新1.random一一对应
        // 原1.next = 原3  =》新1.next = 新3(这个地址就可以根据原3来取得)
        for (Node x = head;x != null;x = x.next) {
            // 新链表的random和next和原链表一一对应
            // 对于Map来说，Key都是原链表的节点
            // 原1.next = 原3
            nodeMap.get(x).next = nodeMap.get(x.next);
            // 原1.random = 原5
            nodeMap.get(x).random = nodeMap.get(x.random);
        }
        // 返回新链表的头结点，就是原链表的head的映射
        return nodeMap.get(head);
    }
}